/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年12月01日
*   描    述：
*   Copyright (C) 2018 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if( len == 0 ){
            return 0;
        }

        vector<int> tmp;
        tmp.push_back(nums[0]);
        for(int i = 1; i < len; i++){
            int k = 0, j = tmp.size();
            int m = 0;
            while( k < j ){
                m = ( j - k )/2 + k;
                if( tmp[m] < nums[i] )
                    k = m + 1;
                else
                    j = m;
            }

            if( k == tmp.size() )
                tmp.push_back(nums[i]);
            else
                tmp[k] = nums[i];
        }

        return tmp.size();
    }
};
